import java.util.HashSet;
import java.util.Stack;

/**
 * 143. 重排链表
 */
public class No143 {
    public void reorderList(ListNode head) {
        // 找到中间指针
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转右侧链表
        ListNode pre = null, cur = slow, nex;
        while (cur != null) {
            nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }

        // 插入到左侧
        while (pre.next != null) {
            ListNode temp1 = head.next;
            ListNode temp2 = pre.next;
            head.next = pre;
            pre.next = temp1;
            head = temp1;
            pre = temp2;
        }
    }
}
